package com.ayuer.chapter05;


import java.util.PriorityQueue;

@SuppressWarnings("all")
public class HeapPriorityQueue implements Queue<Priority> {

//    PriorityQueue
    Priority[] array;
    int size = 0;
    int capacity;

    public HeapPriorityQueue(int capacity) {
        array = new Priority[capacity];
        this.capacity = capacity;
    }


    /**
     * 威廉姆斯建堆算法，更优秀的建堆算法还有Floyd的算法
     * 1.加入新元素。加入到数组的末尾
     * 2.不断比较上浮比较新加元素的父元素的优先级
     *      如果父节点优先级低，则向下潜，找到下一个parent
     *      直到父节点优先级更高，或者child == 0
     * @param e
     * @return
     */
    @Override
    public boolean offer(Priority priority) {
        if (isFull()) {
            return false;
        }

        int childIndex = size++;
        int parentIndex = (childIndex - 1) / 2;
        while (childIndex > 0 && priority.getPriority() > array[parentIndex].getPriority()) {
            //上浮
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = priority;
        return true;
    }

    /**
     * 1.从堆顶开始，与最后一个元素进行交换，移除最后一个元素
     * 2.调整堆结构，下潜
     *      从堆顶开始，将父元素与两个孩子的较大的元素进行交换
     *      直到父元素大于两个孩子元素，或者没有孩子为止
     * @return
     */
    @Override
    public Priority poll() {
        Priority head = array[0];
        //最后的节点上移
        array[0] = array[size - 1];
        array[size--] = null;//gc
        //从索引0开始存储，节点i的父节点存在(i-1)/2，i>0时
        //节点i的左子节点为2i+1，右节点为2i+2
        int parentIndex = 0;
        int leftIndex;
        int rightIndex;
        int max = parentIndex;
        while (true) {
            leftIndex = 2 * max + 1;
            rightIndex = 2 * max + 2;
            if (leftIndex < size && array[max].getPriority() < array[leftIndex].getPriority()) {
                max = leftIndex;
            }
            if (rightIndex < size && array[max].getPriority() < array[rightIndex].getPriority()) {
                max = rightIndex;
            }
            if (max != parentIndex) {
                Priority temp = array[max];//big
                array[max] = array[parentIndex];
                array[parentIndex] = temp;
                parentIndex = max;
            } else {
                break;
            }
        }

        return head;
    }

    @Override
    public Priority peek() {
        return array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return capacity == size;
    }
}
